﻿//#define _CRT_SECURE_NO_WARNINGS 1
//#pragma once
//#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//#include <stdbool.h>
//#include <assert.h>
////堆结构
//typedef struct Heap {
//	int* a;
//	int size;
//	int capacity;
//}Heap;
//void Swap(int* x, int* y);
////向上调整建小堆
//void AdjustUp(int* a, int child);
////向下调整建小堆
//void AdjustDown(int* a, int n, int parent);
////堆的初始化
//void HeapInit(Heap* p);
////创建空堆
//Heap* HeapCreat(int n);
////将数据x放入堆p中
//void HeapPush(Heap* p, int x);
////删除堆的首元素
//void HeapPop(Heap* p);
////判断堆是否为空
//bool HeapEmpty(Heap* p);
////销毁堆
//void HeapDestory(Heap* p);
//void Swap(int* x, int* y) {
//	int t = *x;
//	*x = *y;
//	*y = t;
//}
////建立小堆的调整算法
//void AdjustUp(int* a, int child) {
//	assert(a);
//	int parent = (child - 1) / 2;
//	while (parent >= 0) {
//		if (a[parent] > a[child]) {
//			Swap(a + parent, a + child);
//			child = parent;
//			parent = (child - 1) / 2;
//		}
//		if (a[parent] <= a[child]) {
//			return;
//		}
//	}
//}
////建立小堆的调整算法
//void AdjustDown(int* a, int n, int parent) {
//	assert(a);
//	int child = parent * 2 + 1;
//	while (child < n) {
//		if (child + 1 < n && a[child] > a[child + 1]) {
//			child++;
//		}
//		if (a[child] < a[parent]) {
//			Swap(a + child, a + parent);
//			parent = child;
//			child = parent * 2 + 1;
//		}
//		if (a[child] >= a[parent]) {
//			return;
//		}
//	}
//}
//void HeapInit(Heap* p) {
//	assert(p);
//	p->a = 0;
//	p->size = p->capacity = 0;
//}
//Heap* HeapCreat(int n) {
//	Heap* p = (Heap*)malloc(sizeof(Heap));
//	HeapInit(p);
//	p->a = (int*)malloc(sizeof(int) * n);
//	p->capacity = n;
//	memset(p->a, 0, sizeof(int) * n);
//	return p;
//}
//void HeapPush(Heap* p, int x) {
//	assert(p);
//	//当数据满了之后要扩容
//	if (p->size == p->capacity) {
//		p->a = (int*)realloc(p->a, sizeof(int) * p->capacity * 2);
//		p->capacity *= 2;
//	}
//	p->a[p->size++] = x;
//	//加入数据后要将其调整，要保证加入数据后还是小堆
//	AdjustUp(p->a, p->size - 1);
//}
//void HeapPop(Heap* p) {
//	assert(p);
//	if (!p->size) {
//		return;
//	}
//	//将开头元素与末尾交换，然后再删除末尾元素就相当删除开头元素了
//	Swap(p->a, p->a + p->size - 1);
//	p->size--;
//	//删除后，这时的首元素相当于之前的末尾元素，这时就要将其元素向下调整
//	AdjustDown(p->a, p->size, 0);
//}
//void HeapPrint(Heap* p) {
//	assert(p);
//	for (int i = 0; i < p->size; i++) {
//		fprintf(stdout, "%d ", p->a[i]);
//	}
//	puts("");
//}
//bool HeapEmpty(Heap* p) {
//	assert(p);
//	return p->size == 0;
//}
//void HeapDestory(Heap* p) {
//	free(p->a);
//	free(p);
//}
//int main() {
//	//创建拥有4个元素的空堆
//	Heap* p = HeapCreat(4);
//	//将以下的数据加入小堆中
//	for (int i = 2; i < 7; i++) {
//		HeapPush(p, i - 1);
//		HeapPush(p, i + 2);
//	}
//	//输出
//	HeapPrint(p);
//	return 0;
//}

//void Swap(int* x, int* y) {
//	int t = *x;
//	*x = *y;
//	*y = t;
//}
//void AdjustUp(int* a, int child) {
//	assert(a);
//	int parent = (child - 1) / 2;
//	while (parent >= 0) {
//		//调整建小堆
//		if (a[parent] > a[child]) {
//			Swap(a + parent, a + child);
//			child = parent;
//			parent = (child - 1) / 2;
//		}
//		if (a[parent] <= a[child]) {
//			return;
//		}
//	}
//}
//void AdjustDown(int* a, int n, int parent) {
//	assert(a);
//	int child = parent * 2 + 1;
//	while (child < n) {
//		//调整建小堆
//		if (child + 1 < n && a[child] > a[child + 1]) {
//			child++;
//		}
//		if (a[child] < a[parent]) {
//			Swap(a + child, a + parent);
//			parent = child;
//			child = parent * 2 + 1;
//		}
//		if (a[child] >= a[parent]) {
//			return;
//		}
//	}
//}
//void HeadSort(int* a, int n) {
//	//运用向上调整算法建小堆
//	for (int i = 1; i < n; i++) {
//		AdjustUp(a, i);
//	}
//	//end是堆中最后一个元素的下标
//	int end = n - 1;
//	while (end > 0) {
//		//将堆中最大数据排到最后
//		Swap(&a[0], &a[end]);
//		//将end个数据建成堆 
//		AdjustDown(a, end, 0);//因为根节点的左右子树都可看成小堆，所以只要向下调节根结点就可使end个数据成为小堆
//		//因为后面排好了一个数据，继续将剩下的数据建堆排序即可
//		end--;
//	}
//}
//int main() {
//	int a[] = { 5,10,9,4,3,8,7,1,2,6 };
//	HeadSort(a, sizeof(a) / sizeof(int));
//	for (int i = 0; i < sizeof(a) / sizeof(int); i++) {
//		printf("%d ", a[i]);
//	}
//	return 0;
//}